/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 21:57
 */


// [编程题]01背包

// 求当前背包最多能装多大重量的物品?（没有要求把背包装满）

import java.util.*;


public class test {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int V, int n, int[][] vw) {
        //要注意 vw数组和dp数组的区别
        //vw[i][0]代表的是第i-1个物品的体积，vw[i][1]代表的是第i-1个物品的体重
        //但是对于我 新创建的dp数组来说：dp[i][j]中i的含义就是第i个物品，j就是容量
        //所以在进行，vw数组和dp数组的关联使用的时候，应该注意让dp数组中的i-1才能得到正确的在vw中对应的i物品的值


        // write code here
        //动态规划
        int[][] dp=new int[n+1][V+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=V;j++){

                // 把第i个物品放进背包中的情况：
                //对应的状态转移方程：a1=dp[i-1][j-vw[i-1][0]]+vw[i-1][1];
                int a1=0;
                if(j-vw[i-1][0]>=0){
                    a1=dp[i-1][j-vw[i-1][0]]+vw[i-1][1];
                }

                // 把第i个物品不放进背包中的情况：
                //对应的状态转移方程：a2=dp[i-1][j];
                int a2=dp[i-1][j];

                //然后比较a1和a2的值，选出较大值作为dp[i][j]的值
                dp[i][j]=a1>a2?a1:a2;
            }
        }

        return dp[n][V];
    }
}